// 默认配置
const DEFAULT_CONFIG = {
	id: 'id', // 默认的id字段名
	children: 'children', // 默认的子节点字段名
	pid: 'pid', // 默认的父节点id字段名
};

// 获取配置。  Object.assign 从一个或多个源对象复制到目标对象
const getConfig = (config) => Object.assign({}, DEFAULT_CONFIG, config); // 合并默认配置和用户配置

// 将列表转换为树形结构
export function listToTree(list, config = {}) {
	const conf = getConfig(config); // 获取配置
	const nodeMap = new Map(); // 创建一个新的Map对象
	const result = []; // 初始化结果数组
	const { id, children, pid } = conf; // 解构配置对象

	// 遍历列表，将每个节点添加到nodeMap中
	for (const node of list) {
		node[children] = node[children] || []; // 如果节点没有children字段，则初始化为空数组
		nodeMap.set(node[id], node); // 将节点添加到nodeMap中
	}
	// 遍历列表，将每个节点添加到其父节点的children数组中，如果没有父节点，则添加到结果数组中
	for (const node of list) {
		const parent = nodeMap.get(node[pid]); // 获取父节点
		(parent ? parent[children] : result).push(node); // 将节点添加到父节点的children数组中，如果没有父节点，则添加到结果数组中
	}
	return result; // 返回结果数组
}

// 将树形结构转换为列表
export function treeToList(tree, config = {}) {
	config = getConfig(config); // 获取配置
	const { children } = config; // 解构配置对象
	const result = [...tree]; // 初始化结果数组
	for (let i = 0; i < result.length; i++) {
		if (!result[i][children]) continue; // 如果节点没有children字段，则跳过当前循环
		result.splice(i + 1, 0, ...result[i][children]); // 将节点的children数组插入到结果数组中
	}
	return result; // 返回结果数组
}

// 在树形结构中查找节点
export function findNode(tree, func, config = {}) {
	config = getConfig(config); // 获取配置
	const { children } = config; // 解构配置对象
	const list = [...tree]; // 初始化列表
	for (const node of list) {
		if (func(node)) return node; // 如果节点满足条件，则返回节点
		node[children] && list.push(...node[children]); // 如果节点有children字段，则将children数组添加到列表中
	}
	return null; // 如果没有找到满足条件的节点，则返回null
}

// 在树形结构中查找所有满足条件的节点
export function findNodeAll(tree, func, config = {}) {
	config = getConfig(config); // 获取配置
	const { children } = config; // 解构配置对象
	const list = [...tree]; // 初始化列表
	const result = []; // 初始化结果数组
	for (const node of list) {
		func(node) && result.push(node); // 如果节点满足条件，则将节点添加到结果数组中
		node[children] && list.push(...node[children]); // 如果节点有children字段，则将children数组添加到列表中
	}
	return result; // 返回结果数组
}

// 在树形结构中查找满足条件的路径
export function findPath(tree, func, config = {}) {
	config = getConfig(config); // 获取配置
	const path = []; // 初始化路径数组
	const list = [...tree]; // 初始化列表
	const visitedSet = new Set(); // 创建一个新的Set对象
	const { children } = config; // 解构配置对象
	while (list.length) {
		const node = list[0]; // 获取列表的第一个节点
		if (visitedSet.has(node)) {
			// 如果节点已经被访问过，则从路径数组中移除节点，并从列表中移除节点
			path.pop();
			list.shift();
		} else {
			// 如果节点没有被访问过，则将节点添加到路径数组中，并将节点添加到已访问集合中
			visitedSet.add(node);
			node[children] && list.unshift(...node[children]); // 如果节点有children字段，则将children数组添加到列表的开头
			path.push(node);
			if (func(node)) {
				// 如果节点满足条件，则返回路径数组
				return path;
			}
		}
	}
	return null; // 如果没有找到满足条件的路径，则返回null
}

// 在树形结构中查找所有满足条件的路径
export function findPathAll(tree, func, config = {}) {
	config = getConfig(config); // 获取配置
	const path = []; // 初始化路径数组
	const list = [...tree]; // 初始化列表
	const result = []; // 初始化结果数组
	const visitedSet = new Set(), // 创建一个新的Set对象
		{ children } = config; // 解构配置对象
	while (list.length) {
		const node = list[0]; // 获取列表的第一个节点
		if (visitedSet.has(node)) {
			// 如果节点已经被访问过，则从路径数组中移除节点，并从列表中移除节点
			path.pop();
			list.shift();
		} else {
			// 如果节点没有被访问过，则将节点添加到路径数组中，并将节点添加到已访问集合中
			visitedSet.add(node);
			node[children] && list.unshift(...node[children]); // 如果节点有children字段，则将children数组添加到列表的开头
			path.push(node);
			func(node) && result.push([...path]); // 如果节点满足条件，则将路径数组添加到结果数组中
		}
	}
	return result; // 返回结果数组
}

// 过滤树形结构
export function filter(
	tree,
	func,
	// Partial 将 T 中的所有属性设为可选
	config = {}
) {
	// 获取配置
	config = getConfig(config);
	const children = config.children;

	// 定义列表过滤函数
	function listFilter(list) {
		return list
			.map((node) => ({ ...node })) // 创建节点的浅拷贝
			.filter((node) => {
				// 递归调用 对含有children项  进行再次调用自身函数 listFilter
				node[children] = node[children] && listFilter(node[children]);
				// 执行传入的回调 func 进行过滤
				return func(node) || (node[children] && node[children].length); // 如果节点满足条件，或者节点的children数组不为空，则返回true
			});
	}

	return listFilter(tree); // 返回过滤后的树形结构
}

// 遍历树形结构
export function forEach(tree, func, config = {}) {
	config = getConfig(config); // 获取配置
	const list = [...tree]; // 初始化列表
	const { children } = config; // 解构配置对象
	for (let i = 0; i < list.length; i++) {
		//func 返回true就终止遍历，避免大量节点场景下无意义循环，引起浏览器卡顿
		if (func(list[i])) {
			return;
		}
		children && list[i][children] && list.splice(i + 1, 0, ...list[i][children]); // 如果节点有children字段，则将children数组插入到列表中
	}
}

/**
 * @description: 提取树指定结构
 */
export function treeMap(treeData, opt) {
	return treeData.map((item) => treeMapEach(item, opt)); // 遍历树形结构，对每个节点调用treeMapEach函数
}

/**
 * @description: 提取树指定结构
 */
export function treeMapEach(data, { children = 'children', conversion }) {
	const haveChildren = Array.isArray(data[children]) && data[children].length > 0; // 判断节点是否有children字段
	const conversionData = conversion(data) || {}; // 转换节点数据
	if (haveChildren) {
		// 如果节点有children字段，则递归调用treeMapEach函数
		return {
			...conversionData,
			[children]: data[children].map((i) =>
				treeMapEach(i, {
					children,
					conversion,
				})
			),
		};
	} else {
		// 如果节点没有children字段，则返回转换后的节点数据
		return {
			...conversionData,
		};
	}
}

/**
 * 递归遍历树结构
 * @param treeDatas 树
 * @param callBack 回调
 * @param parentNode 父节点
 */
export function eachTree(treeDatas, callBack, parentNode = {}) {
	treeDatas.forEach((element) => {
		const newNode = callBack(element, parentNode) || element; // 调用回调函数处理节点
		if (element.children) {
			// 如果节点有children字段，则递归调用eachTree函数
			eachTree(element.children, callBack, newNode);
		}
	});
}

/**
 * 筛选 树形结构
 * @param {array} nodes 列表
 * @param {string||number} query 需要查询的值
 * @params {string} column 字段名
 * @param {number} type 1：带父节点，2:不带父节点
 * @returns
 */
export function filterTree(nodes, query, column, type) {
	// 定义过滤条件：节点的指定字段包含查询关键字
	let predicate = function (node) {
		return node[column]?.includes(query);
	};

	// 如果节点为空或长度为0，结束递归
	if (!(nodes && nodes.length)) {
		return [];
	}

	let newChildren = [];
	for (let node of nodes) {
		// 带父节点的情况
		// 如果子孙节点中存在符合条件的，或者节点本身符合条件，将节点加入到新子节点集中
		if (type == 1) {
			let subs = filterTree(node.children, query, column, type);
			if (predicate(node) || (subs && subs.length)) {
				node.children = subs;
				newChildren.push(node);
			}
		} else {
			// 不带父节点的情况
			// 只需要考虑节点本身是否满足条件，如果满足条件，将节点加入到新子节点集中，并递归过滤其子节点
			// 如果不满足条件，递归过滤其子节点并将结果加入到新子节点集中
			if (predicate(node)) {
				node.children = filterTree(node.children, query, column, type);
				newChildren.push(node);
			} else {
				newChildren.push(...filterTree(node.children, query, column, type));
			}
		}
	}
	// 如果新子节点集为空，返回空数组，否则返回新子节点集
	return newChildren.length ? newChildren : [];
}
